package com.dylan.历史.算法;

import java.util.Arrays;

/**
 * @Auther: ankang
 * @Date: 2019/1/15 10:08
 * @Description:
 */
public class 排列组合 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        System.out.println("---------------- 排列 --------------");
        permutation(arr, 0, arr.length - 1);
        System.out.println("---------------- 组合 --------------");
        combination(arr, 0, new int[1]);
    }

    /**
     * 打印数组的排列
     * @param arr 待打印的数组
     * @param start 排序的起始位置
     * @param end 排序的终止位置
     */
    private static void permutation(int[] arr, int start, int end) {
        // 到达递归终止条件时，打印数组
        if (start == end) {
            System.out.println(Arrays.toString(arr));
        }
        // 将每一个元素都与其实位置进行交换，然后对除起始元素的部分进行递归排列
        for (int i = start; i <= end; i++) {
            // 交换
            swap(arr, start, i);
            // 对除起始元素的部分进行递归排列
            permutation(arr, start + 1, end);
            // 还原交换
            swap(arr, start, i);
        }
    }

    /**
     * 打印数组的组合
     * @param arr 待打印的数组
     * @param start 挑选下一个组合元素的起始位置
     * @param arr2 用于存放组合结果的数组
     */
    private static void combination(int[] arr, int start, int[] arr2) {
        // 循环从指定位置开始往下挑选组合元素
        for (int i = start; i < arr.length; i++) {
            // 将挑选的组合元素放到最后
            arr2[arr2.length - 1] = arr[i];
            // 打印当前组合
            System.out.println(Arrays.toString(arr2));
            // 复制新的数组，比之前多一位
            int[] arr3 = Arrays.copyOf(arr2, arr2.length + 1);
            // 当前挑选组合元素后，继续递归挑选
            combination(arr, i + 1, arr3);
        }
    }


    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}
